package _剑指offer.二叉树;

import util.TreeNode;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

public class _07_重建二叉树 {
    @Test
    public void main() {
        int[] array1 = new int[]{3, 9, 20, 15, 7};
        int[] array2 = new int[]{9, 3, 15, 20, 7};
        TreeNode root = buildTree(array1, array2);
        TreeNode.printTree(root);
    }
    
    private Map<Integer, Integer> indexMap = new HashMap<>();
    
    public TreeNode buildTree(int[] preOrder, int[] inOrder) {
        // 构建 中序遍历的 map
        int n = preOrder.length;
        for (int i = 0; i < n; i++) {
            indexMap.put(inOrder[i], i);
        }
        return myBuildTree(preOrder, inOrder, 0, n - 1, 0, n - 1);
    }
    
    public TreeNode myBuildTree(int[] preOrder, int[] inOrder, int preOrderLeft, int preOrderRight, int inOrderLeft, int inOrderRight) {
        // 递归结束条件
        if (preOrderLeft > preOrderRight) return null;
        
        // 构建根节点
        TreeNode root = new TreeNode(preOrder[preOrderLeft]);
        
        // 获取 中序遍历中的 根节点 索引
        int inOrderRootIndex = indexMap.get(preOrder[preOrderLeft]);
        // 获得 左子树的 节点数  由于不包含 根节点 所以是 b-a 不用 +1
        int leftSize = inOrderRootIndex - inOrderLeft;
        
        // 递归构建左右子树
        root.left  = myBuildTree(preOrder, inOrder, preOrderLeft+1, preOrderLeft+leftSize, inOrderLeft, inOrderLeft+leftSize);
        root.right = myBuildTree(preOrder, inOrder, preOrderLeft+leftSize+1, preOrderRight, inOrderRootIndex+1, inOrderRight);
        
        return root;
    }
    
    /**
     * 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
     * 返回树的最大深度 3 。
     */
    public static class _55_1_二叉树的深度 {
        @Test
        public void main() {
            Integer[] input = new Integer[]{3, 9, 20, null, null, 15, 7};
            TreeNode root = TreeNode.getTreeFromArray(input);
            System.out.println("maxDepth(root) = " + maxDepth(root));
        }
        
        public int maxDepth(TreeNode root) {
            if (root == null) return 0;
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
    }
}
